package Tree.SegmentTree;

/*
    线段树
 */
public class SegmentTree {
    private int m;
    private Segment segments[];

    public SegmentTree(int m) {
        this.m = m;
        segments = new Segment[4 * m];
        buildSegmentTreeInterval(1, m, 1);
    }

    private void buildSegmentTreeInterval(int left, int right, int i) {
        segments[i] = new Segment();
        segments[i].left = left;
        segments[i].right = right;
        segments[i].count = 0;
        if (left == right) return;
        int mid = (left + right) / 2;
        buildSegmentTreeInterval(left, mid, i * 2);
        buildSegmentTreeInterval(mid + 1, right, i * 2 + 1);
    }

    //i是索引，因为采用的是数组来存储，所以可以通过下标直接访问
    public void insert(int data) {
        int left = 1;
        int right = m;
        int i = 1;
        while (left != right) {
            segments[i].count++;
            int mid = (left + right) / 2;
            if (data <= mid) {
                right = mid;
                i = i * 2;
            } else {
                left = mid + 1;
                i = i * 2 + 1;
            }
        }
        segments[i].count++;
    }

    public void delete(int data) {
        int left = 1;
        int right = m;
        int i = 1;
        while (left != right) {
            segments[i].count--;
            int mid = (left + right) / 2;
            if (data <= mid) {
                right = mid;
                i = i * 2;
            } else {
                left = mid + 1;
                i = i * 2 + 1;
            }
        }
        segments[i].count--;
    }

    //查询区间统计数据
    public int count(int left, int right) {
        return countInterval(left, right, 1);
    }

    //对于一个给定的区间，我们可以把它分割，一直分割到和线段树中节点的区间相同，然后返回节点的count
    //即使没有直接相同的节点也没有关系，可以多个区间，每个区间的总数之和就是总区间要统计的数
    private int countInterval(int left, int right, int i) {
        //刚好区间重合
        if (segments[i].left == left && segments[i].right == right) {
            return segments[i].count;
        }
        int mid = (segments[i].left + segments[i].right) / 2;
        if (left > mid) {
            return countInterval(left, right, i * 2 + 1);
        } else if (right <= mid) {
            return countInterval(left, right, i * 2);
        } else {//没有重合的区间，那就拆分
            return countInterval(left, mid, i * 2)
                    + countInterval(mid + 1, right, i * 2 + 1);
        }
    }
}

/*  线段树节点
    区间左端，区间右端，统计量（例如区间内元素的个数）
 */
class Segment {
    public int left;
    public int right;
    public int count;
}